1
效率之尺:为什么大 O 记法是程序员的通用语?
AI028 Lesson 2
00:00

时间复杂度 (Time Complexity) 并非衡量算法运行的绝对秒数,而是一种描述算法运行时间随问题规模 $n$ 增长而增长的数学函数。它建立在“算法分析是一种独立于实现的算法度量方法”这一核心原则之上。

规模 n 时间 T(n) O(n²) O(n) O(log n) O(1)

为什么它是通用语?

  • 量化演进:大 O 记法忽略低阶项和常数,仅聚焦于数量级 (Order of Magnitude)
  • 度量的确定性:程序员通常以最坏情况 (Worst Case) 作为基准,为性能提供下限保障。
  • 跨环境决策:无论是在超级计算机还是嵌入式芯片,从 $O(n^2)$ 优化到 $O(n \log n)$ 的收益都是本质性的。
计数法 (Counting)
计算两个字符串中每个字符出现的次数。如果字符计数列表相同,那么两个字符串肯定是异序词。这种方法实现了 计数法: $O(n)$ 的高效性。